package niuke;

import java.util.LinkedList;

/**
 * description:
 * author:张腾
 * date:2021-06-29
 */
public class NC49 {
    public int longestValidParentheses (String s) {
        // write code here
        int max = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i)==')'){
                if (s.charAt(i-1)=='(')
                    dp[i] = (i>=2?dp[i-2]:0)+2;
                else if (i-dp[i-1]>0 && i-dp[i-1]-1=='(')
                    dp[i] = dp[i-1]+(i-dp[i-1]>=2?dp[i-dp[i-1]-2]:0)+2;

                max = Math.max(max,dp[i]);
            }
        }
        return max;
    }
}
